package leetbook.math;


public class Solution204 {

    public static void main(String[] args) {
        System.out.println(countPrimes(10));
    }

    public static int countPrimes(int n) {
        //埃氏筛法
        boolean[] notPrime = new boolean[n+1];
        int cur = 2; //当前的筛子
        while (cur*cur<n){ //当前筛子的平方大于n说明已经筛完了
            for (int i = 2*cur; i <= n; i+=cur) { //把cur的倍数置为非质数
                notPrime[i] = true;
            }
            //选下一个筛子
            while (++cur<=n&&notPrime[cur]);
        }
        int res = 0, i = 2;
        while (i<=n){
            if(!notPrime[i]) res++;
            i++;
        }
        return res;
    }
}
